package B.链表;

import java.util.ArrayList;

public class _206_反转链表 {
    /**
     *自解：从头开始遍历每一个结点 每一个结点存在arrayList
     * 通过 但是耗时太久
     *
    *
     */
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null ){
            return head;
        }
        ListNode p = head;
        ArrayList<ListNode> list = new ArrayList<>();
        while (p.next !=null) {
            list.add(p);
            p=p.next;
        }
        ListNode re = p;

        for (int i=list.size();i>0;i--) {

            p.next = list.get(i - 1);
            p = p.next;
        }
        p.next =null;

        return re;

    }

    /**
     * 迭代--逆转就是目前的前指针指向前一个 但单链表无法记住前一个 故此时需要preNode用来存储前一个
     * @param head
     * @return
     */
    public ListNode reverseList1(ListNode head){
        ListNode preNode =null;
        ListNode curNode = head;//用于遍历的结点

        while (curNode != null){
            ListNode nextTemp = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextTemp;
        }

        return preNode;//proNode才有先后次序体现 所以返回改制

    }

    /**
     * 递归---没看懂
     * 返回条件 ：如果 head 为空或者 head.next 为空，则说明没有节点或者只有一个节点了，返回本节点即可。
     * 假设 head 节点的 后一个节点 node 节点已经反转好了，只需要改变 node 的下一个节点指向 head 同时 head 的下一个节点指向 null
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode node = reverseList(head.next);//head的后一个节点已经反转好
        head.next.next = head;
        head.next = null;
        return node;
    }

}

